package com.lw.leetcode.tree.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1377. T 秒后青蛙的位置
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/23 13:18
 */
public class FrogPosition {

    private Map<Integer, List<Integer>> map = new HashMap<>();

    public double frogPosition(int n, int[][] edges, int t, int target) {
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            map.computeIfAbsent(a, v -> new ArrayList<>()).add(b);
            map.computeIfAbsent(b, v -> new ArrayList<>()).add(a);
        }
        if (1 == target) {
            List<Integer> list = map.get(1);
            if ( list == null) {
                return 1;
            } else {
                return 0;
            }
        }

        List<Integer> list = find(target, 0, 1);
        if(list == null) {
            return 0;
        }
        int size = list.size();
        if (size > t ||  (size < t && map.get(target).size() > 1)) {
            return 0;
        }
        double item = map.get(1).size();
        for (int i = list.size() - 1; i > 0; i--) {
            item *= (map.get(list.get(i)).size() - 1);
        }
        return 1 / item;
    }

    private List<Integer> find(int t, int f, int key) {
        List<Integer> list = map.get(key);
        if(list == null) {
            return null;
        }
        for (Integer v : list) {
            if (v == f) {
                continue;
            }
            if (v == t) {
                List<Integer> values = new ArrayList<>();
                values.add(v);
                return values;
            }
            List<Integer> values = find(t, key, v);
            if (values != null) {
                values.add(v);
                return values;
            }
        }
        return null;
    }

}
